package day3;

import java.util.*;

/*
3-2
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 */
public class TestDemo3 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int count = 1;
        int a = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if(count != 0) {
                if(numbers[i] == a) {
                    count++;
                }else {
                    count--;
                }
            }else {
                a = numbers[i];
                count = 1;
            }
        }
        count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if(numbers[i] == a) {
                count++;
            }
        }
        return (count > numbers.length / 2) ? a:0;
    }
//    public int MoreThanHalfNum_Solution1 (int[] numbers) {
//        // write code here
//        Arrays.sort(numbers);
//        if(numbers.length == 1) return numbers[0];
//        int a = numbers[numbers.length / 2];
//        return a;
}
